package exam.bfs;


import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * https://leetcode-cn.com/problems/perfect-squares/
 *
 * 描述
 * Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
 *
 * Example 1:
 *
 * Input: n =
 * 12
 * Output: 3
 * Explanation:
 * 12 = 4 + 4 + 4.
 * Example 2:
 *
 * Input: n =
 * 13
 * Output: 2
 * Explanation:
 * 13 = 4 + 9.
 *
 * @author shenenlu 2021年05月20日 下午17:56:41
 */
public class PerfectSquares {

    static Set<Integer> sett = new HashSet<>();

    public static void main(String[] args) {
        System.out.println(aaa(12));
    }

    public static int aaa(int n){
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        int step=0;
        while( !q.isEmpty() ){
            step++;
            int cnt= q.size();
            while( cnt-- > 0 ){   //逐层入队
                int num = q.element();
                q.poll();
                for(int i=1; i*i <= n-num; i++){
                    int a = num + i * i;
                    if( a > n ) break;
                    if( a==n ) return step;
                    if( !sett.contains(a) ){  //剪枝
                        q.offer(a);  //将平方数的和入队以保存状态
                        sett.add(a);
                    }
                }
            }
        }
        return 0;
    }

}
